%% Useful tools which everybody loves

nl :- write_character(0'\n).

member(E,[E|_]).
member(E,[_|Es]) :- member(E,Es).

append([],Y,Y).
append([X|Xs],Y,[X|Zs]) :- append(Xs,Y,Zs).

revappend([],Y,Y).
revappend([X|Xs],Y,Zs) :- revappend(Xs,[X|Y],Zs).

reverse(XS,SX) :- revappend(XS,[],SX).

select(E,[E|Xs],Xs).
select(E,[X|Xs],[X|Ys]) :- select(E,Xs,Ys).

split([Pivot|Rest],Pivot,[]-Rest).
split([L|Rest],Pivot,[L|Ls]-Rs) :- L \= Pivot, split(Rest,Pivot,Ls-Rs). %% Why is that \= there?


sort(Key,List,Sorted) :- qsort(Key,List,Sorted,[]).

qsort(Key,[X|L],R,R0) :-
	partition(Key,L,X,L1,L2),
	qsort(Key,L2,R1,R0),
	qsort(Key,L1,R,[X|R1]).
qsort(_,[],R,R).

partition(Key,[X|L],Y,[X|L1],L2) :-
	apply(Key,[X,Xk]), apply(Key,[Y,Yk]), Xk >= Yk, !,
	partition(Key,L,Y,L1,L2).
partition(Key,[X|L],Y,L1,[X|L2]) :-
	partition(Key,L,Y,L1,L2).
partition(_,[],_,[],[]).


